\section{GZIP Parallelisierung} \label{sec:gzipParallelisierung}
In diesem Kapitel wird die eigentliche Aufgabenstellung der Seminararbeit behandelt. Danach folgt die Problembeschreibung mit genauerer Erläuterung des GZIP Algorithmus und den Parallelisierungsmöglichkeiten von GZIP. Im weiteren Verlauf wird die Umsetzung und die Vorgehensweise beschrieben und auf Hindernisse und Probleme hingewiesen.\\

\subsection{Aufgabenstellung}
Das Programm GZIP (Version 1.2.4) soll so verändert werden, dass es sich die Rechenleistung moderner PCs zu Nutze macht, in dem es die Komprimierungsarbeit auf mehrere Prozessorkerne verteilt und somit parallel abarbeitet.\\

\subsection{Problembeschreibung}
GZIP wurde in der Programmiersprache C verfasst. Bekanntermaßen zählt C zu den prozeduralen Programmiersprachen. In seinen früheren Formen (C90 - C99) unterstützte C kein Multi-Threading \cite{c99}. Dies und die Tatsache, dass GZIP auf einem sequenziellen Algorithmus basiert sind nicht zuletzt die Gründe dafür, dass GZIP die Komprimierung der übergebenen Dateien rein sequenzielle durchführt.\\
Als ein Beispiel unter vielen bietet es sich an GZIP zu modernisieren, den Ablauf zu parallelisieren und die sich daraus ergebenden Unterschiede aufzuzeigen. Um ein besseres Verständnis von GZIP und den Problemen bei der Parallelisierung zu vermitteln wird im Folgenden der Deflate Komprimierungsalgorithmus, der von GZIP verwendet wird, genauer vorgestellt.\\

\subsubsection{Deflate Algorithmus}$\;$ \\
Der Deflate Algorithmus ist eine Kombination aus dem LZ77 Algorithmus und der Huffman-Koodierung. Beide werden in diesem Kapitel genauer beschrieben.\\
\newline
\textbf{LZ77 Algorithmus} \label{textbf:LZ77} \\
Der LZ77 Algorithmus wurde 1977 von Abraham Lempel und Jacob Ziv entwickelt. Die Komprimierung verwendet dabei wiederkehrende Muster innerhalb der Daten. Der Algorithmus betrachtet jedoch nicht die kompletten Daten, sondern nur einen Ausschnitt (ein Fenster), das standardmäßig eine Größe von 32 Kilobyte hat. Dieses wird dann über den Input Stream geschoben und der entsprechend Bereich komprimiert (Sliding Window).\\
\begin{figure}[h!]
    \includegraphics[width=\textwidth]{images/LZ77_Match}
    \caption[LZ77 Match Beispiel]{LZ77 Match Beispiel}
    \label{fig:lz77}
\end{figure}\\
Die Komprimierung selbst erfolgt durch ein relativ simples Prinzip. Es werden wiederkehrenden Bytefolgen gesucht. Werden Wiederholungen gefunden, so werden diese durch einen Zeiger auf das erste Auftreten der Bytefolge ersetzt.\\
\newline
Abbildung \ref{fig:lz77} zeigt grafisch die Funktionsweise des Algorithmus. 
Um weiter Speicherplatz zu sparen wird in diesem Beispiel folgender Eintrag gespeichert: 100011[D=6,L=6]. Wobei D die Distanz bis zur nächsten Übereinstimmung darstellt und L für die Länge der Übereinstimmung steht. \cite{alg_gzip}\\
\newline
\textbf{Huffman Kodierung} \\
Die Huffman Kodierung wurde 1952 von David A. Huffman entwickelt. Er beschreibt die Kodierung von Quellsymbolen, in diesem Fall Bytes oder Chars, in Codewörter unterschiedlicher länge. Die Speicherung erfolg hierbei in so genannten Huffman Trees, wobei die einzelnen Blätter das kodierte Zeichen darstellen und der Pfad von der Wurzel zum Blatt das entsprechende Codewort. Huffman Bäume werden von den Blättern zur Wurzel gebildet, wobei die Häufigkeit des Vorkommens der unterschiedlichen Quellsymbole berücksichtigt wird.\\
\begin{figure}[h!]
    \centering
    \includegraphics[width=0.5\textwidth]{images/huffman_tree}
    \caption[Huffman Baum Beispiel]{Huffman Baum Beispiel}
    \label{fig:huffman_tree}
\end{figure}\\
Bei dem in Abbildung \ref{fig:huffman_tree} dargestellten Beispiel wurde der Satz \glqq ein Glas Wein bitte\grqq in einen Huffman Baum transformiert. Es ist zu erkennen, dass Buchstaben, die häufiger vorkommen ein kürzeres Codeword haben, als solche die z.B. nur einmal auftauchen. Weiterhin ist zu erkennen, dass es sich hierbei um B-Bäume handelt, also Bäume bei denen jeder Knoten maximal zwei Blätter bzw. Kind-Knoten besitzt.\\
\clearpage
\noindent Der ursprüngliche Huffman Baum ist jedoch kein B-Baum, sondern ein k-nären Wurzelbaum. Hierbei hat jeder Knoten maximal k Blätter bzw. Kind-Knoten. Das in diesem Beispiel ein binärer Baum verwendet wurde liegt daran, dass in GZIP auch ausschließlich B-Bäume verwendet werden. \cite{huffman}\\
\newline
Wie bereits erwähnt ist der Deflate Algorithmus eine Kombination aus LZ77 und der Huffman Kodierung. Im folgenden soll nun das Zusammenspiel dieser beiden Algorithmen genauer beschrieben werden.\\
Der Trick im Deflate Algorithmus liegt in der Größe der Huffmann Bäume. Die Codewortlänge wird auf 15 beschränkt. Das bedeutet alle generierten Bäume haben eine maximale Tiefe von 15. Dies wird durch die Aufteilung der Struktur, die sich aus der LZ77 Komprimierung ergibt (Bsp.: 100011[D=6,L=6]), erreicht. Dabei werden die Entfernung und die Länge in unterschiedlichen Bäumen gespeichert. Weiterhin wird die Entfernung auf 32.506 (speziell für GZIP) und die Länge auf 258 beschränkt. Die Länge einer Übereinstimmung muss mindestens 3 betragen. Außerdem werden nur die Längen und Entfernungen im Baum gespeichert, die auch wirklich bei der Komprimierung auftreten.\\
Um die Geschwindigkeit zu erhöhen verwendet GZIP \glqq lazy evaluation\grqq. Dabei wird bei einer Übereinstimmung geprüft, ob diese \glqq gut genug\grqq bzw. \glqq lang genug\grqq ist. Diese Genauigkeit kann über Startparameter beeinflusst werden. GZIP bietet somit die Möglichkeit die Datenreduktion und die Geschwindigkeit des Komprimierungsalgorithmus zu beeinflussen. Durch diese Startparameter ist es möglich die Genauigkeit der Suche nach Überein-stimmungen zu erhöhen oder zu verringern. Dies beeinflusst natürlich auch die Geschwindigkeit des Programms. Um so größer die Variable \glqq lang genug\grqq ist, um so genauer wird das Fenster nach Übereinstimmungen durchsucht und folglich verlängert sich die Ausführungs-zeit von GZIP. Dadurch wird jedoch auch ein höherer Komprimierungsfaktor erreicht. \cite{gzip_deflate}\\
Letztlich ist immer der Anwendungsfall für die benötigten Einstellungen entscheidend.\\
\clearpage

\subsection{Parallelisierungsmöglichkeiten von GZIP}
GZIP (in der Version 1.2.4) bietet zwei Bereiche, in denen Parallelisierung sinnvoll eingebaut bzw. eingesetzt werden kann. Diese Bereiche werden im Folgenden etwas genauer erläutert.

\subsubsection{Parallelisierung der Dateiverarbeitung}$\;$ \label{subsub:parallelisierungDateiverarbeitung} \\
Den ersten Bereich stellt das parallele Komprimieren der einzelnen Dateien dar. Wie im Kapitel \ref{subsec:gzip} beschrieben komprimiert GZIP jeweils immer nur einzelne Dateien. Mit dem Parameter '-r' ist es jedoch möglich einen Ordner anzugeben, dessen Inhalt komprimiert werden soll. Das heißt, GZIP komprimiert sequenziell alle Dateien die sich im angegebenen Verzeichnis und etwaigen Unterverzeichnissen befinden. Der Parallelisierungsansatz ist nun die Komprimierung der einzelnen Dateien parallel in mehreren Threads auf mehreren Prozessorkernen auszuführen und dadurch die Dauer des Gesamtprozesses zu verringern. Die parallele Ausführung ist möglich, da die Komprimierung der einzelnen Dateien unabhängig voneinander stattfindet.\\

\subsubsection{Parallelisierung des Algorithmus}$\;$ \\
Als zweite Möglichkeit der Parallelisierung bietet sich der Komprimierungsalgorithmus selbst an. Wie bereits in Kapitel \ref{textbf:LZ77} erwähnt, wird zur Komprimierung ein Fenster über den Input Stream geschoben, der Inhalt komprimiert und in einem Huffman Baum gespeichert.\\
Die Idee ist nun nicht mehr ein Fenster über den Input Stream zu schieben, sonder die Daten in unabhängige Blöcke zu unterteilen und einzeln, parallel zu Komprimieren. Diese Idee wird im Kapitel \ref{sec:Parallelisierung des Algorithmus} verfolgt und die Umsetzung für GZIP (1.2.4) genauer beschrieben.

\subsection{Umsetzung}
In den hier folgenden Unterkapiteln wird die Umsetzung der oben beschriebenen Ideen detailliert beschrieben.\\

\input{input}
\input{algorithm}
\input{benchmark}
\input{hindernisseProbleme}




